package cn.whdream.datastructure.sort;

import java.util.Arrays;



/**
 * 
 * @author admin
 * 归并算法
 */
public class MergetSort {
	public static void main(String[] args) {
		int arr[] = {8,4,5,7,1,3,6,2};
		int temp[] = new int[arr.length];
		mergeSort(arr,0,arr.length-1,temp);
		print(arr);
	}
	private static void print(int[] arr) {
		System.out.println(Arrays.toString(arr));
	}
	/**
	 * 
	 * @param arr 原数组
	 * @param left 左边开始的位置
	 * @param right 右边边界值的index的位置
	 *    eg: {1,2,3} left:0 ,right:2 即切分好的数组的，最后一个
	 * @param temp 临时的存放数组
	 */
	private static void mergeSort(int[] arr, int left, int right, int[] temp) {
		/*
		 *划定切分的条件，递归时如果切到最后，两者相同时；停止递归 
		 */
		if (left < right) {
			//切分出一个中间 index
			int mid = (left+right)/2;
			//将左边的数组进行归并排序
			mergeSort(arr, left, mid, temp);
			//右边的部分进行排序
			mergeSort(arr, mid+1, right, temp);
			//将有序的两边统一进行一次排序，合并成一个数组
			merge(arr,left,mid,right,temp);
		}
	}
	/**
	 * 
	 * @param arr 原数组
	 * @param left 左边开始的位置
	 * @param right 右边结束边界的位置
	 * @param temp 临时的存放数组
	 */
	private static void merge(int[] arr, int left, int mid, int right, int[] temp) {
		int i = left;
		int j = mid+1; 
		int t = 0;
		//先限定一个 循环的范围
		while( i <= mid && j<=right ) {
			if(arr[i] <= arr[j]) {
				temp[t] = arr[i];
				t++;
				i++;
			}else {
				temp[t] = arr[j];
				t++;
				j++;
			}
		}
		//2.比较过后，则开始进行剩余的数据拷贝到temp当中
		//左边有剩余就将左边的拷贝进去
		while(i <= mid) {
			temp[t] = arr[i];
			t++;
			i++;
		}
		//右边有剩余，就将右边的拷贝进去
		while(j <= right) {
			temp[t] = arr[j];
			t++;
			j++;
		}
		//重新排序后，将目前temp的全部拷贝回去
		t = 0;
		int tempLeft = left;
		while(tempLeft <= right) {
			arr[tempLeft] = temp[t];
			t++;
			tempLeft++;
		}
	}
	
	
}
